from functools import cache
from typing import List


class Solution:
    """
     方法： 使用动态规划判断字符串是否可以被拆分成字典中的单词
            f[i]表示字符串s的前i个字符是否可以被拆分
            对于每个位置i，枚举最后一个单词的起始位置j
            如果f[j]为真且s[j:i]在字典中，则f[i]为真
     
     Args:
         s: str - 需要判断的字符串
         wordDict: List[str] - 包含可用单词的字典
     
     Returns:
         bool: 字符串是否可以被拆分成字典中的单词
     
     Time: O(n * m) - 其中n是字符串长度，m是字典中最长单词的长度
     
     Space: O(n) - 需要一个长度为n的数组存储动态规划状态
     """
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        max_len = max(map(len, wordDict))
        words = set(wordDict)

        n = len(s)
        f = [True] + [False] * n
        for i in range(1, n+1):
            for j in range(i - 1, max(i - max_len - 1, -1), -1):
                if f[j] and s[j:i] in words:
                    f[i] = True
                    break
        return f[n]

    def wordBreak1(self, s: str, wordDict: List[str]) -> bool:
        max_len = max(map(len, wordDict))
        words = set(wordDict)

        @cache  # 缓存装饰器，避免重复计算 dfs 的结果（记忆化）
        def dfs(i: int) -> bool:
            if i == 0:
                return True
            for j in range(i - 1, max(i - max_len - 1, -1), -1):
                if s[j:i] in words and dfs(j):
                    return True
            return False
        return dfs(len(s))